#include <bits/stdc++.h>

using namespace std;

// 含有嵌套的分子式求原子数量
// 测试链接 : https://leetcode.cn/problems/number-of-atoms/

class Solution 
{
private:
    int where;

    void fill(map<string, int>& ans, string& name, map<string, int>& pre, int cnt)
    {
        if(!name.empty() || !pre.empty())
        {
            cnt = cnt == 0 ? 1 : cnt;
            if(!name.empty())
            {
                ans[name] += cnt;
            }
            else
            {
                for(auto& [key, c] : pre)
                {
                    ans[key] += c * cnt;
                }
            }
        }
    }

	// s[i....]开始计算，遇到字符串终止 或者 遇到 ) 停止
	// 返回 : 自己负责的这一段字符串的结果，有序表！
	// 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    map<string, int> f(string& s, int i)
    {
        // ans是总表
        map<string, int> ans;
        // 之前收集到的名字，历史一部分
        string name;
        // 之前收集到的有序表，历史一部分
        map<string, int> pre;
        // 历史翻几倍
        int cnt = 0;
        while(i < s.size() && s[i] != ')')
        {
            if(s[i] >= 'A' && s[i] <= 'Z' || s[i] == '(')
            {
				fill(ans, name, pre, cnt);
                name.clear();
                pre.clear();
                cnt = 0;
                if(s[i] >= 'A' && s[i] <= 'Z')
                {
                    name += s[i++];
                }
                else // 遇到了左括号
                {
                    pre = f(s, i + 1);
                    i = where + 1;
                }   
            }
            else if(s[i] >= 'a' && s[i] <= 'z')
                name += s[i++];
            else
                cnt = 10 * cnt + s[i++] - '0';
        }

        fill(ans, name, pre, cnt);
        where = i;
        return ans;
    }

public:
    string countOfAtoms(string s) 
    {
        where = 0;
        map<string ,int>&& m = f(s, 0);
        string ans;
        for(auto& [key, cnt] : m)
        {
            ans += key;
            if(cnt > 1) ans += to_string(cnt);
        }
        return ans;
    }
};